This invention relates to joining tables in databases, and in particular to hash join method of joining tables in databases.
Relational database store information as tables or relations. For example, in a database schema describing an organization, one relation may store information describing employees and another relation may store information describing departments. Each row of the department relation may represent a department and each row of the employee relation may represent an employee. Each relation may have a key that identifies a particular entity represented in the relation. For example, each employee may be associated with a key value that uniquely identifies the employee. Key values that identify employees can be employee id or social security numbers of employees. Similarly, the department relation may have a key based on the department name or a unique department id. The employee information may refer to a department associated with the employee using the corresponding department id. A user that wants to retrieve information combining the employee and department relation may issue a join query that specifies a join clause relating fields from the relation being joined.
Various techniques are used by databases to perform joins of tables including nested-loop join, sort-merge join, and hash join. A hash join algorithm typically builds a hash table for one of the relations and probes the hash table for each record of the other table in the join relation. For performance reasons it is preferable to store the data structures used in the hash-join process in memory rather than on persistent storage e.g., disk. However, several scenarios cause the hash-join process to run out of memory, thereby requiring the structures to be stored on disk. This causes the performance of the queries based on the hash join process to be degraded. Bad performance of queries often requires analysis by experts to determine how to speed up the queries and may consume significant resources of development and support teams of an organization.